package com.Algorithm.prim;

import java.util.Arrays;

/**
 * Prim算法求最小生成树
 *
 * @author MaoLin Wang
 * @date 2019/11/1614:20
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;

        //-1表示不连通
        int weight[][] = new int[][]{
                {-1, 5, 7, -1, -1, -1, 2},
                {5, -1, -1, 9, -1, -1, 3},
                {7, -1, -1, -1, 8, -1, -1},
                {-1, 9, -1, -1, -1, 4, -1},
                {-1, -1, 8, -1, -1, 5, 4},
                {-1, -1, -1, 4, 5, -1, 6},
                {2, 3, -1, -1, 4, 6, -1}
        };

        MGraph graph = new MGraph(verxs);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        minTree.print(graph);
        /*
            [-1, 5, 7, -1, -1, -1, 2]
            [5, -1, -1, 9, -1, -1, 3]
            [7, -1, -1, -1, 8, -1, -1]
            [-1, 9, -1, -1, -1, 4, -1]
            [-1, -1, 8, -1, -1, 5, 4]
            [-1, -1, -1, 4, 5, -1, 6]
            [2, 3, -1, -1, 4, 6, -1]
         */

        minTree.prim(graph, 0);


    }
}

//最小生成树
class MinTree {
    //创建图的邻接矩阵

    /**
     * @param mGraph 图对象
     * @param verxs  顶点个数
     * @param data   顶点的值
     * @param wight  邻接矩阵
     */
    public void createGraph(MGraph mGraph, int verxs, char[] data, int[][] wight) {
        int i, j;
        for (i = 0; i < verxs; i++) {
            mGraph.data[i] = data[i];
            for (j = 0; j < verxs; j++) {
                mGraph.weight[i][j] = wight[i][j];
            }
        }
    }

    public void print(MGraph mGraph) {
        for (int[] link : mGraph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * @param mGraph
     * @param v      从图的第一个定义开始生成
     */
    public void prim(MGraph mGraph, int v) {
        //定点是否被访问过,默认为0，访问过为1
        int visited[] = new int[mGraph.verxs];

        visited[v] = 1;
        //记录两个定点的下标
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000;
        for (int k = 1; k < mGraph.verxs; k++) {//prim算法后有versx-1条边
            //确定每一次生成的子图，和哪个节点的距离最近
            for (int i = 0; i < mGraph.verxs; i++) {//i表示被访问过的节点
                for (int j = 0; j < mGraph.verxs; j++) {//j表示未访问过的节点
                    if (visited[i] == 1 && visited[j] == 0 && mGraph.weight[i][j]!=-1&& mGraph.weight[i][j] < minWeight) {
                     /*
                               [10000, 5, 7, 10000, 10000, 10000, 2]
                                [5, 10000, 10000, 9, 10000, 10000, 3]
                                [7, 10000, 10000, 10000, 8, 10000, 10000]
                                [10000, 9, 10000, 10000, 10000, 4, 10000]
                                [10000, 10000, 8, 10000, 10000, 5, 4]
                                [10000, 10000, 10000, 4, 5, 10000, 6]
                                [2, 3, 10000, 10000, 4, 6, 10000]
                             */
                        minWeight = mGraph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }

            System.out.println("边<" + mGraph.data[h1] + "," + mGraph.data[h2] + ">权值为:" + minWeight);

            //将当前节点标记为已经访问
            visited[h2] = 1;
            minWeight = 10000;
        }

    }
}

class MGraph {
    int verxs;//图的节点数
    char[] data;//节点数据
    int[][] weight;//边的权值

    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}
